﻿//给定一个长度为 n 的整数数组 height 。
//有 n 条垂线，第 i 条线的两个端点是(i, 0) 和(i, height[i]) 。
//找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
//返回容器可以储存的最大水量。
//
//说明：你不能倾斜容器。
//
//输入：[1, 8, 6, 2, 5, 4, 8, 3, 7]
//输出：49
//解释：图中垂直线代表输入数组[1, 8, 6, 2, 5, 4, 8, 3, 7]。
//在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
//
//输入：height = [1, 1]
//输出：1
//
//提示：
//	n == height.length
//	2 <= n <= 10^5
//	0 <= height[i] <= 10^4

// class Solution {
// public:
//     int maxArea(vector<int>& height) {
//         int n = height.size();
//         int ret = 0;
//         // 两层for枚举出所有可能出现的情况

//         for (int i = 0; i < n; i++) {
//             for (int j = i + 1; j < n; j++) {
//                 // 计算容积，找出最⼤的那⼀个
//                 ret = max(ret, min(height[i], height[j]) * (j - i));
//             }
//         }
//         return ret;
//     }
// };

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1, ret = 0;
        while (left < right) {
            int v = min(height[left], height[right]) * (right - left);
            ret = max(ret, v);
            // 移动指针
            if (height[left] < height[right])
                left++;
            else
                right--;
        }
        return ret;
    }
};